package com.note.feng.leetcode.algorithms.easy;

public class SixtyNine {

    /**
     * 69 x的平方根
     *
     * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
     *
     * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
     *
     * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
     *
     * 示例 1：
     *
     * 输入：x = 4
     * 输出：2
     * 示例 2：
     *
     * 输入：x = 8
     * 输出：2
     * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
     *
     * 提示：
     *
     * 0 <= x <= 231 - 1
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/sqrtx
     */

    /**
     *解法：
     * 二分法：每次得到中间数，需要判断：
     * 1、若mid * mdi == x，直接返回mid
     * 2、若mid * mid > x，则继续遍历区间[left, mid - 1]
     * 3、若mid* mid < x，如果（mid + 1） * (mid + 1) > x，直接返回mid，否则继续遍历区间[mid + 1, right]
     * 若遍历结束，直接返回left
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        if(x < 2){
            return x;
        }
        int left = 0;
        int right = x;
        while (left < right){
            int mid = (right - left) / 2 + left;
            if(x / mid == mid){
                return mid;
            }else if(x / mid > mid){
                if(x / (mid + 1) < mid + 1){
                    return mid;
                }
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }
}
